//给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [1,2,3,4,5,6,7], k = 3
//输出: [5,6,7,1,2,3,4]
//解释:
//向右轮转 1 步: [7,1,2,3,4,5,6]
//向右轮转 2 步: [6,7,1,2,3,4,5]
//向右轮转 3 步: [5,6,7,1,2,3,4]
// 
//
// 示例 2: 
//
// 
//输入：nums = [-1,-100,3,99], k = 2
//输出：[3,99,-1,-100]
//解释: 
//向右轮转 1 步: [99,-1,-100,3]
//向右轮转 2 步: [3,99,-1,-100] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// -2³¹ <= nums[i] <= 2³¹ - 1 
// 0 <= k <= 10⁵ 
// 
//
// 
//
// 进阶： 
//
// 
// 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。 
// 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？ 
// 
//
// Related Topics 数组 数学 双指针 👍 2022 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2023-11-10 17:58:50
 * @description 189.轮转数组
 */
public class RotateArray{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new RotateArray().new Solution();
		 int[] nums = {1, 2, 3, 4, 5, 6, 7};
		 solution.rotate(nums,3);
		 System.out.println(Arrays.toString(nums));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*1.额外空间，直接赋值，空间时间On
		 * 2.环状替换
		 * 3.旋转*/
	/*時間空間On*/
    public void rotate1(int[] nums, int k) {
		int [] ar=new int[nums.length];
		k=k%nums.length;
		System.arraycopy(nums,0,ar,0,nums.length);
		for (int i = 0; i <nums.length ; i++) {
			nums[(i+k)%nums.length]=ar[i];
		}
    }
	/*环状替换，*/
	public void rotate2(int[] nums, int k) {
		int n=nums.length;
		k=k%n;
		//t是Index,交换临时变量tem，pre前一个位置的值，len计数改变了多少个
		int i=-1,tem=0,pre=0,len=n,t=0;
		while (len>0){
			i++;
			t=i;
			pre=nums[i];
			do{
				//保留
				tem=nums[(t+k)%n];
				//改变现在
				nums[(t+k)%n]=pre;
				//保留现在
				pre=tem;
				t+=k;
				len--;
			}
			//一直循环，直到回到出发点
			while ((t)%n!=i);

		}
	}
	/*环状数组*/
	public void rotate3(int[] nums, int k) {
		int n=nums.length;
		k=k%n;
		int count=gcd(n,k);
		for (int i = 0; i < count; i++) {
			int cur=i;
			int pre=nums[i];
			do{
				int next=(cur+k)%n;
				int tem=nums[next];
				nums[next]=pre;
				pre=tem;
				cur=next;
			}while (i!=cur);
		}
	}
	public int gcd(int x,int y){
		return y>0?gcd(y,x%y):x;
	}
		//旋转数组,
	public void rotate(int[] nums, int k) {
		k%=nums.length;

		//向右
		reverse(nums,0,nums.length-1);
		reverse(nums,0,k-1);
		reverse(nums,k,nums.length-1);
//向左写法1
//		reverse(nums,0,nums.length-1);
//		reverse(nums,0,nums.length-k-1);
//		reverse(nums,nums.length-k,nums.length-1);
		//向左写法2
//		reverse(nums,0,k-1);
//		reverse(nums,0,nums.length-1);
//		reverse(nums,0,nums.length-k-1);
	}
	public void reverse(int []nums,int l,int r){
		while (l<r){
			int t=nums[l];
			nums[l]=nums[r];
			nums[r]=t;
			l++;
			r--;
		}
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
